import java.util.*;

public class BrinarySearchTree {
    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int key) {
            this.key = key;
        }
    }

    public TreeNode root;

    /**
     * 插入一个元素
     * @param key
     */
    public boolean insert(int key) {
        if(root == null){
            root = new TreeNode(key);
            return true;
        }
        TreeNode node = new TreeNode(key);
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null){
            if(cur.key < key){
                parent = cur;
                cur = cur.right;
            }else if(cur.key > key){
                parent = cur;
                cur = cur.left;
            }else{
                System.out.println("已有该数");
                return false;
            }
        }
        if(parent.key < key){
            parent.right = node;
        }
        if(parent.key > key){
            parent.left = node;
        }

        return true;
    }

    //查找key是否存在
    public TreeNode search(int key) {
        if(root == null) return null;
        TreeNode cur = root;
        while(cur != null){
            if(cur.key < key){
                cur = cur.right;
            } else if (cur.key > key) {
                cur = cur.left;
            }else{
                System.out.println("找到了");
                return cur;
            }
        }
        return null;
    }
    //删除key的值
    public boolean remove(int key) {
        if(root == null) return false;
        TreeNode cur = new TreeNode(key);
        TreeNode parent = null;
        while(cur != null){
            if(cur.key < key){
                parent = cur;
                cur = cur.right;
            } else if (cur.key > key) {
                parent = cur;
                cur = cur.left;
            }else{
                //这里找到了，开始删除
                removeKey(parent,cur);
                return true;
            }
        }
        return false;
    }

    //删除数据
    private void removeKey(TreeNode parent, TreeNode cur) {
        if(cur.right == null && cur.left == null){
            if(parent.left == cur){
                parent.left = null;
            }else{
                parent.right = null;
            }
        }
        if(cur.left == null){
            if(root == cur){
                root = cur.right;
            }else if (parent.left == cur){
                parent.left = cur.right;
            }else{
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if(root == cur){
                root = cur.left;
            }else if (parent.left == cur){
                parent.left = cur.left;
            }else{
                parent.right = cur.left;
            }
        }else{
            //此时，要么放左子树的最大值，要么放右子树的最小值
            TreeNode parentN = cur;
            TreeNode curN = cur.left;
            while(curN.right != null){
                parentN = curN;
                curN = curN.right;
            }
            cur.key = curN.key;
            parentN.right = null;
        }
    }

    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        int count = 0;
        for(int i = 0; i < jewels.length(); i++){
            if(!set.contains(jewels.charAt(i))){
                set.add(jewels.charAt(i));
            }
        }
        for(int i = 0; i < stones.length(); i++){
            if(set.contains(stones.charAt(i))){
                count++;
            }
        }
        return count;
    }

    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        for (String word : words) {
            cnt.put(word, cnt.getOrDefault(word, 0) + 1);
        }
        List<String> rec = new ArrayList<String>();
        for (Map.Entry<String, Integer> entry : cnt.entrySet()) {
            rec.add(entry.getKey());
        }
        Collections.sort(rec, new Comparator<String>() {
            public int compare(String word1, String word2) {
                return cnt.get(word1) == cnt.get(word2) ? word1.compareTo(word2) : cnt.get(word2) - cnt.get(word1);
            }
        });
        return rec.subList(0, k);
    }

}
